Chapter 4. Shor’s Factorization Algorithm

The algorithms discussed so far (Deutsch-Jozsa, Simon) had a strong conceptual nature, proving that quantum computers could be faster than classical computers. This algorithm, published by Peter Shor in 1994, demonstrated that practical and important problems, namely factoring large numbers, could be solved at speeds classical computers could not achieve (from exponential to polynomial time).

Since the security of current internet cryptographic standards (RSA) is based on the assumption that “factoring large numbers is very difficult,” this algorithm is regarded as the most important algorithm that initiated the era of quantum computing.

The core of Shor’s algorithm is to use the Quantum Fourier Transform (QFT) learned in Chapter 3 to convert the “factorization problem” into a “period-finding” problem and solve it.

1. Fundamental Concepts

  • Problem: Factoring: Given a very large composite number \(N\), the problem is to find prime numbers \(p\) and \(q\) such that \(N = p \times q\). Classically, it takes exponential time relative to the number of bits of \(N\).

  • Step 1 (Classical): Convert Factoring to Period Finding: The first genius insight of Shor’s algorithm is showing that this problem is mathematically equivalent to “finding the period of a function.”

    1. Choose an arbitrary number \(a < N\) that is coprime with \(N\). (\(\text{gcd}(a, N) = 1\))
    2. Define the function \(f(x) = a^x \pmod N\).
    3. This function has a minimum period \(r\) satisfying \(a^r \equiv 1 \pmod N\).
    4. If this \(r\) is found and \(r\) is even, \(a^r - 1 = (a^{r/2} - 1)(a^{r/2} + 1) \equiv 0 \pmod N\)
    5. This implies that \((a^{r/2} - 1)(a^{r/2} + 1)\) is a multiple of \(N\).
    6. Therefore, \(\text{gcd}(a^{r/2} - 1, N)\) or \(\text{gcd}(a^{r/2} + 1, N)\) is likely to be a factor of \(N\) (either \(p\) or \(q\)).

    Summary: Factoring (\(N\)) ⟹ Finding the period (\(r\)) of \(f(x) = a^x \pmod N\). What is difficult for a classical computer is factoring \(N\), and what is difficult for a quantum computer is finding \(r\).

  • Step 2 (Quantum): Period Finding (The Quantum Core): Classically, finding \(r\) is as difficult as factoring \(N\) directly. However, quantum computers can efficiently find this period using the QFT learned in Chapter 3.

  1. Preparation: Prepare two registers, \(|x\rangle\) (input) and \(|y\rangle\) (output).
    \(|\psi_0\rangle = |0\rangle |0\rangle\)
  2. Superposition: Apply the H gate to the input register to create a superposition of all \(x\). ( \(N_q = 2^n\) )
    \(|\psi_1\rangle = \left( \frac{1}{\sqrt{N_q}}\sum_{x=0}^{N_q-1} |x\rangle \right) |0\rangle\)
  3. Quantum Parallelism (Modular Exponentiation): Apply the oracle \(U_f\) that computes \(f(x) = a^x \pmod N\). This \(U_f\) circuit (modular exponentiation) is complex but can be implemented in polynomial time.
    \(|\psi_2\rangle = U_f |\psi_1\rangle = \frac{1}{\sqrt{N_q}}\sum_{x=0}^{N_q-1} |x\rangle |a^x \pmod N\rangle\)
  4. Measurement (State Collapse): Measure the output register \(|a^x \pmod N\rangle\).
    • The measurement result yields some value \(k\). (Example: \(k = a^{x_0} \pmod N\))
    • Due to this measurement, the input register’s state collapses into a superposition of \(x\) values satisfying \(f(x)=k\). Since \(f(x)\) has period \(r\), these \(x\) values are \(x_0, x_0 + r, x_0 + 2r, \dots\).
    • \(|\psi_3\rangle = \left( \frac{1}{\sqrt{M}}\sum_{j=0}^{M-1} |x_0 + jr\rangle \right) |k\rangle \quad\) (M approximates \(N_q/r\))
  5. QFT (Frequency Extraction): Now, the input register is in a state with a perfect period \(r\). Apply the inverse quantum Fourier transform (QFT\(^\dagger\)) to this state.
    • Fourier transforming a signal in the “time” domain with period \(r\) produces peaks at multiples of the frequency \(1/r\).
    • \(\text{QFT}^\dagger |\psi_3\rangle \implies\) the measurement result \(c\) is likely to satisfy \(\frac{c}{N_q} \approx \frac{m}{r}\) (where \(m\) is an integer).
  6. Measurement (Result): Measure the input register to obtain the value \(c\).

  • Step 3 (Classical): Continued Fractions Algorithm:
    We want \(r\), but the quantum computer provides \(c\). We only know the approximation \(\frac{c}{N_q} \approx \frac{m}{r}\).
    The continued fractions algorithm is a highly efficient classical algorithm that finds the reduced fraction \(\frac{m}{r}\) that best approximates the decimal \(\frac{c}{N_q}\).

    • Using this algorithm, \(r\) can be determined with high probability.

2. Symbols and Key Equations

  • Problem: \(N=pq\)
    • Classical Reduction: Select an \(a\) such that \(\text{gcd}(a, N)=1\), find the period \(r\) of \(f(x) = a^x \pmod N\).
    • Period Condition: \(a^r \equiv 1 \pmod N\)
    • Factors: \(\text{gcd}(a^{r/2} \pm 1, N)\)
    • Quantum Oracle: \(U_f |x\rangle |y\rangle = |x\rangle |y \oplus (a^x \pmod N)\rangle\) (or \(|x\rangle |a^x \pmod N\rangle\))
    • Core State Collapse: \(\frac{1}{\sqrt{N_q}}\sum_{x} |x\rangle |a^x \pmod N\rangle \xrightarrow{\text{Measure } |k\rangle} \frac{1}{\sqrt{M}}\sum_{j} |x_0 + jr\rangle\)
    • QFT\(^\dagger\) Result: \(\text{QFT}^\dagger (\sum_j |x_0 + jr\rangle) \implies\) measurement value \(c\) is \(c \approx m \frac{N_q}{r}\) ( \(m \in \{0, 1, \dots, r-1\}\) )
    • Classical Post-processing: \(\frac{c}{N_q} \approx \frac{m}{r} \xrightarrow{\text{Continued Fractions}} r\)

3. Easy Example: Factorizing N=15 (Virtual Simulation)

  • Problem: Factorize \(N=15\). (We know the classical answer is 3, 5.)

  • 1st Step (Classical):

    1. Randomly choose \(a=7\). (\(\text{gcd}(7, 15)=1\), OK)
    2. Our goal: Find the period \(r\) of \(f(x) = 7^x \pmod{15}\).
    • (Precomputed: \(7^0=1, 7^1=7, 7^2=49\equiv 4, 7^3=28\equiv 13, 7^4=91\equiv 1\). The period is \(r=4\). A quantum computer must find this ‘4’.)

  • 2nd Step (Quantum):

  1. Preparation: Assume an \(n=4\)-bit (\(N_q=16\)) input register is used to handle \(N=15\). (In reality, \(N^2\)-near, i.e., 8 bits, is needed, but for conceptual explanation, it is simplified to \(n=4\).)
    1. Superposition: \(|\psi_1\rangle = \frac{1}{\sqrt{16}}\sum_{x=0}^{15} |x\rangle |0\rangle\)
    2. Oracle: \(U_f\) performs parallel computation of \(f(x)=7^x \pmod{15}\). \(|\psi_2\rangle = \frac{1}{4} \Big( |0\rangle|1\rangle + |1\rangle|7\rangle + |2\rangle|4\rangle + |3\rangle|13\rangle + |4\rangle|1\rangle + |5\rangle|7\rangle + \dots \Big)\)
    3. Measurement (Collapse): Measure the output register. Suppose we are fortunate and measure \(k=1\).
    4. The input register collapses into a superposition of \(x\) values where \(f(x)=1\), i.e., \(x=0, 4, 8, 12\). \(|\psi_3\rangle = \frac{1}{\sqrt{4}}(|0\rangle + |4\rangle + |8\rangle + |12\rangle)\)
    5. QFT\(^\dagger\) (Frequency Extraction): Apply \(\text{QFT}_{16}^\dagger\) to this periodic \(r=4\) state.
      • Theoretically, this transformation creates an equal superposition of states where \(m \cdot (N_q/r) = m \cdot (16/4) = 4m\), i.e., \(|0\rangle, |4\rangle, |8\rangle, |12\rangle\).

  • 💡 Detailed Explanation (Principle of QFT Finding the Period)

    The \(|\psi_3\rangle\) state is a “period-4 comb-like wave”. In Chapter 3, it was mentioned that QFT transforms the time (position) domain into the frequency domain.

    • \(\text{QFT}(\text{period } r \text{ wave}) = \text{period } N_q/r \text{ wave}\)

    Since \(r=4, N_q=16\), \(\text{QFT}^\dagger\) creates a state with period \(16/4 = 4\). That is, the measurement result \(c\) will be one of \(0, 4, 8, 12\). (These are the \(c\) values where constructive interference occurs for all \(x\) with \(e^{-2\pi i xc / 16}\).)

  • Step 3 (Classical):

    1. Measurement: Suppose we measure the input register and obtain \(c=8\) (0 has no information, so retry).
    2. Continued Fraction: We obtained \(\frac{c}{N_q} = \frac{8}{16} = \frac{1}{2}\).
    3. \(\frac{m}{r} = \frac{1}{2}\). Since \(m\) is an integer smaller than \(r\), \(m=1, r=2\) or \(m=2, r=4\) are possible. Choose \(r=4\) by checking whether \(a^{r/2} \not\equiv -1 \pmod N\). (Actually, \(c=4\) (\(m/r=1/4 \to r=4\)) or \(c=12\) (\(m/r=3/4 \to r=4\)) is more likely to occur.)
    4. Assume \(r=4\) is found.

  • Final Computation (Classical):

    • \(r=4\) (even), \(a=7\).
    • \(\text{gcd}(a^{r/2} - 1, N) = \text{gcd}(7^2 - 1, 15) = \text{gcd}(48, 15) = \mathbf{3}\)
    • \(\text{gcd}(a^{r/2} + 1, N) = \text{gcd}(7^2 + 1, 15) = \text{gcd}(50, 15) = \mathbf{5}\)
    • Successfully found the prime factors 3 and 5 of \(N=15\). ### 4. Practice Problems
  1. Classical Reduction: \(N=21\) has been chosen with \(a=4\). Calculate the period \(r\) of \(f(x) = 4^x \pmod{21}\) by hand, and find the factors using \(\text{gcd}(a^{r/2} \pm 1, 21)\).
  2. QFT Result Prediction: In the \(N=15\) (\(r=4\)) example, assume an 8-bit (\(N_q=256\)) register is used. Predict what values of \(c\) will mainly be measured after the QFT\(^\dagger\) measurement.
  3. Algorithm Failure: \(a=14\) has been chosen for \(N=15\). What is the period \(r\), and explain why this \(r\) value cannot find the factors.
  4. Efficiency Comparison: Qualitatively describe the difference between a classical computer (exponential \(O(e^{n^{1/3}})\)) and Shor’s algorithm (polynomial \(O(n^3)\)) when factoring a number with \(n=1000\) bits (\(N \approx 10^{300}\)).

5. Explanations

  1. \(4^1=4\), \(4^2=16\), \(4^3=64=3\cdot 21 + 1 \equiv 1\). The period \(r=3\). Since \(r=3\) is odd, \(r/2\) is not an integer. The computation of \(\text{gcd}(a^{r/2} \pm 1, N)\) cannot be performed. Conclusion: \(a=4\) was a ‘bad’ choice. Return to step 1 of the algorithm and choose another \(a\) (e.g., \(a=2\)).
  2. \(N_q = 256, r=4\). The measured values \(c\) are approximately \(c \approx m \cdot (N_q/r) = m \cdot (256/4) = 64m\). The values \(c=0, 64, 128, 192\) (and values near them) will mainly be measured. (\(c=0\) does not provide useful information.)
  3. \(a=14 \equiv -1 \pmod{15}\). \(14^1 \equiv -1 \equiv 14 \pmod{15}\) \(14^2 \equiv (-1)^2 \equiv 1 \pmod{15}\). The period \(r=2\). Since \(r=2\) is even, proceed to the next step. \(\text{gcd}(a^{r/2} - 1, N) = \text{gcd}(14^{2/2} - 1, 15) = \text{gcd}(14-1, 15) = \text{gcd}(13, 15) = 1\). (Failure) \(\text{gcd}(a^{r/2} + 1, N) = \text{gcd}(14^{2/2} + 1, 15) = \text{gcd}(14+1, 15) = \text{gcd}(15, 15) = 15\). (Failure) This is due to the ‘trivial’ case where \(a^{r/2} \equiv -1 \pmod N\) (i.e., \(14 \equiv -1 \pmod{15}\)). In this case, factors cannot be found either, and you must return to step 1 and choose another \(a\).
  4. When \(n=1000\), classical computers require \(O(e^{c n^{1/3}(\log n)^{2/3}})\), which is much larger than \(O(e^{1000^{1/3}}) \approx O(e^{10})\) (about 22,000). This is effectively longer than the age of the universe, making computation impossible. In contrast, quantum computers require \(O(n^3) = O(1000^3) = 10^9\) (1 billion) operations. This is a computation that can be handled by modern supercomputers in a few seconds to a few minutes. That is, it transforms an ‘impossible’ problem into a ‘possible’ one.